﻿//https://leetcode.cn/problems/merge-k-sorted-lists/?envType=study-plan-v2&envId=top-100-liked

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return mergesort(lists, 0, lists.size() - 1);

    }

    ListNode* mergesort(vector<ListNode*>& lists, int l, int r)
    {
        if (l > r) return nullptr;
        if (l == r) return lists[l];

        //求中间值
        int mid = (l + r) >> 1;

        //左右两部分先合并链表
        ListNode* l1 = mergesort(lists, l, mid);
        ListNode* l2 = mergesort(lists, mid + 1, r);

        //合并左右两部分的链表
        return listmerge(l1, l2);
    }

    ListNode* listmerge(ListNode* l1, ListNode* l2)
    {
        if (l1 == nullptr) return l2;
        if (l2 == nullptr) return l1;

        //合并
        ListNode* ret = new ListNode(0);
        ListNode* tail = ret;
        ListNode* cur1 = l1, * cur2 = l2;
        while (cur1 && cur2)
        {
            if (cur1->val < cur2->val)
            {
                tail->next = cur1;
                tail = cur1;
                cur1 = cur1->next;
            }
            else
            {
                tail->next = cur2;
                tail = cur2;
                cur2 = cur2->next;
            }
        }
        while (cur1)
        {
            tail->next = cur1;
            break;
        }
        while (cur2)
        {
            tail->next = cur2;
            break;
        }

        tail = ret->next;
        delete ret;
        return tail;
    }
};